Ian Jackson [Thu, 14 Dec 2017 16:16:20 +0000 (16:16 +0000)]
libxl: pvshim: Provide first-class config settings to enable shim mode
This is API-compatible because old callers are supposed to call
libxl_*_init to initialise the struct; and the updated function clears
these members.
It is ABI-compatible because the new fields make this member of the
guest type union larger but only within the existing size of that
union.
Unfortunately it is not easy to backport because it depends on the PVH
domain type. Attempts to avoid use of the PVH domain type involved
working with two views of the configuration: the "underlying" domain
type and the "visible" type (and corresponding config info). Also
there are different sets of config settings for PV and PVH, which
callers would have to know to set.
And, unfortunately, it will not be possible, with this approach, to
enable the shim by default for all libxl callers. (Although it could
perhaps be done in xl.)
For now, our config defaults are:
* if enabled, path is "xen-shim" in the xen firmware directory
* if enabled, cmdline is the one we are currently debugging with
The debugging arguments will be rationalised in a moment.
Signed-off-by: Ian Jackson <Ian.Jackson@eu.citrix.com> Signed-off-by: George Dunlap <george.dunlap@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:21 +0000 (11:41 +0000)]
xen/shim: allow DomU to have as many vcpus as available
Since the shim VCPUOP_{up/down} hypercall is wired to the plug/unplug
of CPUs to the shim itself, start the shim DomU with only the BSP
online, and let the guest bring up other CPUs as it needs them.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:21 +0000 (11:41 +0000)]
xen/shim: crash instead of reboot in shim mode
All guest shutdown operations are forwarded to L0, so the only native
calls to machine_restart happen from crash related paths inside the
hypervisor, hence switch the reboot code to instead issue a crash
shutdown.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
[ wei: fix arm build ] Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:20 +0000 (11:41 +0000)]
xen/pvshim: use default position for the m2p mappings
When running a 32bit kernel as Dom0 on a 64bit hypervisor the
hypervisor will try to shrink the hypervisor hole to the minimum
needed, and thus requires the Dom0 to use XENMEM_machphys_mapping in
order to fetch the position of the start of the hypervisor virtual
mappings.
Disable this feature when running as a PV shim, since some DomU
kernels don't implemented XENMEM_machphys_mapping and break if the m2p
doesn't begin at the default address.
NB: support for the XENMEM_machphys_mapping was added in Linux by
commit 7e7750.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
Sergey Dyasli [Thu, 11 Jan 2018 11:45:23 +0000 (11:45 +0000)]
x86/pv-shim: shadow PV console's page for L2 DomU
Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
[remove notify_guest helper and directly use pv_shim_inject_evtchn] Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:19 +0000 (11:41 +0000)]
xen/pvshim: add grant table operations
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Signed-off-by: Anthony Liguori <aliguori@amazon.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:19 +0000 (11:41 +0000)]
xen/pvshim: set correct domid value
If domid is not provided by L0 set domid to 1 by default. Note that L0
not provinding the domid can cause trouble if the guest tries to use
it's domid instead of DOMID_SELF when performing hypercalls that are
forwarded to the L0 hypervisor.
Since the domain created is no longer the hardware domain add a hook
to the domain shutdown path in order to forward shutdown operations to
the L0 hypervisor.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 11:41:18 +0000 (11:41 +0000)]
xen/pvshim: modify Dom0 builder in order to build a DomU
According to the PV ABI the initial virtual memory regions should
contain the xenstore and console pages after the start_info. Also set
the correct values in the start_info for DomU operation.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Andrew Cooper [Wed, 22 Nov 2017 13:31:26 +0000 (13:31 +0000)]
tools/firmware: Build and install xen-shim
Link a minimum set of files to build the shim. The linkfarm rune can
handle creation and deletion of files. Introduce build-shim and
install-shim targets in xen/Makefile.
We can do better by properly generate the dependency from the list of
files but that's an improvement for later.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Sergey Dyasli [Fri, 24 Nov 2017 11:07:32 +0000 (11:07 +0000)]
x86/guest: add PV console code
Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Roger Pau Monne [Tue, 9 Jan 2018 12:51:37 +0000 (12:51 +0000)]
x86/guest: setup event channel upcall vector
And a dummy event channel upcall handler.
Note that with the current code the underlying Xen (L0) must support
HVMOP_set_evtchn_upcall_vector or else event channel setup is going to
fail. This limitation can be lifted by implementing more event channel
interrupt injection methods as a backup.
Register callback_irq to trick toolstack to think the domain is
enlightened.
Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Wei Liu [Thu, 16 Nov 2017 17:56:18 +0000 (17:56 +0000)]
x86: xen pv clock time source
It is a variant of TSC clock source.
Signed-off-by: Wei Liu <wei.liu2@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Roger Pau Monne [Tue, 9 Jan 2018 11:19:44 +0000 (11:19 +0000)]
x86/guest: map shared_info page
Use an unpopulated PFN in order to map it.
Signed-off-by: Roger Pau Monne <roger.pau@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com>
Wei Liu [Wed, 3 Jan 2018 16:50:24 +0000 (16:50 +0000)]
xen/pvshim: keep track of used PFN ranges
Simple infrastructure to keep track of PFN space usage, so that we can
use unpopulated PFNs to map special pages like shared info and grant
table.
As rangeset depends on malloc being ready so hypervisor_setup is
introduced for things that can be initialised late in the process.
Note that the PFN is marked as reserved at least up to 4GiB (or more
if the guest has more memory). This is not a perfect solution but
avoids using the MMIO hole below 4GiB. Ideally the shim (L1) should
have a way to ask the underlying Xen (L0) which memory regions are
populated, unpopulated, or MMIO space.
Signed-off-by: Roger Pau Monne <roger.pau@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Wei Liu [Thu, 11 Jan 2018 10:18:09 +0000 (10:18 +0000)]
xen/console: Introduce console=xen
This specifies whether to use Xen specific console output. There are
two variants: one is the hypervisor console, the other is the magic
debug port 0xe9.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Wei Liu [Tue, 14 Nov 2017 18:19:09 +0000 (18:19 +0000)]
x86/pvh: Retrieve memory map from Xen
Signed-off-by: Wei Liu <wei.liu2@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Andrew Cooper [Wed, 22 Nov 2017 11:09:41 +0000 (11:09 +0000)]
x86/link: Relocate program headers
When the xen binary is loaded by libelf (in the future) we rely on the
elf loader to load the binary accordingly. Specify the load address so
that the resulting binary can make p_vaddr and p_paddr have different
values.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Andrew Cooper [Thu, 11 Jan 2018 17:48:00 +0000 (17:48 +0000)]
x86/fixmap: Modify fix_to_virt() to return a void pointer
Almost all users of fix_to_virt() actually want a pointer. Include the cast
within the definition, so the callers don't need to.
Two users which need the integer value are switched to using __fix_to_virt()
directly. A few users stay fully unchanged, due to GCC's void pointer
arithmetic extension causing the same behaviour. Most users however have
their explicit casting dropped.
Since __iomem is not used consistently in Xen, we drop it too.
No functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Wei Liu <wei.liu2@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Bob Moore [Thu, 11 Jan 2018 17:47:59 +0000 (17:47 +0000)]
ACPICA: Make ACPI Power Management Timer (PM Timer) optional.
PM Timer is now optional.
This support is already in Windows8 and "SHOULD" come out in ACPI 5.0A
(if all goes well).
The change doesn't affect Xen directly, because it does not rely
on the presence of the PM timer.
Signed-off-by: Bob Moore <robert.moore@intel.com> Signed-off-by: Lv Zheng <lv.zheng@intel.com> Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
[ported to Xen] Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Jonathan Ludlam [Thu, 11 Jan 2018 17:47:58 +0000 (17:47 +0000)]
tools/libxc: Multi modules support
Signed-off-by: Jonathan Ludlam <jonathan.ludlam@citrix.com> Signed-off-by: Sergey Dyasli <sergey.dyasli@citrix.com> Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Signed-off-by: Wei Liu <wei.liu2@citrix.com>
Roger Pau Monne [Thu, 11 Jan 2018 17:47:58 +0000 (17:47 +0000)]
xen/x86: report domain id on cpuid
Use the ECX register of the hypervisor leaf 5. The EAX register on
this leaf is a flags field that can be used to notice the presence of
the domain id in ECX. Note that this is only available to HVM guests.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Andrew Cooper [Fri, 3 Nov 2017 16:12:13 +0000 (16:12 +0000)]
x86/cmdline: Introduce a command line option to disable IBRS/IBPB, STIBP and IBPB
Instead of gaining yet another top level boolean, introduce a more generic
cpuid= option. Also introduce a helper function to parse a generic boolean
value.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Fri, 3 Nov 2017 16:12:13 +0000 (16:12 +0000)]
x86/feature: Definitions for Indirect Branch Controls
Contemporary processors are gaining Indirect Branch Controls via microcode
updates. Intel are introducing one bit to indicate IBRS and IBPB support, and
a second bit for STIBP. AMD are introducing IBPB only, so enumerate it with a
separate bit.
Furthermore, depending on compiler and microcode availability, we may want to
run Xen with IBRS set, or clear.
To use these facilities, we synthesise separate IBRS and IBPB bits for
internal use. A lot of infrastructure is required before these features are
safe to offer to guests.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com> Acked-by: Wei Liu <wei.liu2@citrix.com>
Andrew Cooper [Sun, 17 Dec 2017 16:20:50 +0000 (16:20 +0000)]
x86/amd: Try to set lfence as being Dispatch Serialising
This property is required for the AMD's recommended mitigation for Branch
Target Injection, but Xen needs to cope with being unable to detect or modify
the MSR.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Mon, 18 Dec 2017 13:54:25 +0000 (13:54 +0000)]
x86: Support indirect thunks from assembly code
Introduce INDIRECT_CALL and INDIRECT_JMP which either degrade to a normal
indirect branch, or dispatch to the __x86_indirect_thunk_* symbols.
Update all the manual indirect branches in to use the new thunks. The
indirect branches in the early boot and kexec path are left intact as we can't
use the compiled-in thunks at those points.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Mon, 18 Dec 2017 13:54:25 +0000 (13:54 +0000)]
x86: Support compiling with indirect branch thunks
Use -mindirect-branch=thunk-extern/-mindirect-branch-register when available.
To begin with, use the retpoline thunk. Later work will add alternative
thunks which can be selected at boot time.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
Jan Beulich [Tue, 16 Jan 2018 16:50:59 +0000 (17:50 +0100)]
x86: allow Meltdown band-aid to be disabled
First of all we don't need it on AMD systems. Additionally allow its use
to be controlled by command line option. For best backportability, this
intentionally doesn't use alternative instruction patching to achieve
the intended effect - while we likely want it, this will be later
follow-up.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Jan Beulich [Tue, 16 Jan 2018 16:49:03 +0000 (17:49 +0100)]
x86: Meltdown band-aid against malicious 64-bit PV guests
This is a very simplistic change limiting the amount of memory a running
64-bit PV guest has mapped (and hence available for attacking): Only the
mappings of stack, IDT, and TSS are being cloned from the direct map
into per-CPU page tables. Guest controlled parts of the page tables are
being copied into those per-CPU page tables upon entry into the guest.
Cross-vCPU synchronization of top level page table entry changes is
being effected by forcing other active vCPU-s of the guest into the
hypervisor.
The change to context_switch() isn't strictly necessary, but there's no
reason to keep switching page tables once a PV guest is being scheduled
out.
This isn't providing full isolation yet, but it should be covering all
pieces of information exposure of which would otherwise require an XSA.
There is certainly much room for improvement, especially of performance,
here - first and foremost suppressing all the negative effects on AMD
systems. But in the interest of backportability (including to really old
hypervisors, which may not even have alternative patching) any such is
being left out here.
Signed-off-by: Jan Beulich <jbeulich@suse.com> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Andrew Cooper [Fri, 6 Oct 2017 13:21:32 +0000 (13:21 +0000)]
x86/Rules: Use -mskip-rax-setup if the compiler supports it
This option is available from GCC 5 onwards, and was specifically introduced
as an optimisation for Linux. When using variadic functions, the caller needs
to know how many floating point arguments were passed. Xen, like Linux,
doesn't uses floating point arguments, so doesn't need to emit code to inform
variadic functions such as printk() that there are zero arguments.
Andrew Cooper [Fri, 29 Dec 2017 12:56:24 +0000 (12:56 +0000)]
x86/bitops: Introduce variable/constant pairs for __{set,clear,change}_bit()
Just as with test_bit, the non-atomic set/clear/change helpers can be better
optimised by the compiler in the case that the nr parameter is constant, and
it often is.
This results in a general replacement of `mov $imm, %reg; bt* %reg, mem` with
the shorter and more simple `op $imm, mem`, also reducing register pressure.
The net diffstat is:
add/remove: 0/1 grow/shrink: 5/17 up/down: 90/-301 (-211)
As a piece of minor cleanup, drop unnecessary brackets in the test_bit()
macro, and fix the indentation.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Dario Faggioli <dfaggioli@suse.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Fri, 29 Dec 2017 12:56:34 +0000 (12:56 +0000)]
xen/credit2: Drop unnecessary bit test
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: George Dunlap <george.dunlap@citrix.com> Reviewed-by: Dario Faggioli <dfaggioli@suse.com>
c/s b6c2c7f48a unfortunately broke booting on affected systems. Most of the
time, ioemul_handle_quirk() doesn't write a custom stub, and the redundant
call was depending on the seemingly-pointless writing of the default stub.
Alter the ioemul_handle_quirk() API to return a boolean if a custom stub was
written, allowing its caller to know whether it should write a default stub
instead.
Finally, adjust the /* Regular stubs */ comment to make it clearer that the 16
refers to the length of the emul stub opcode.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Tue, 9 Jan 2018 16:28:28 +0000 (16:28 +0000)]
x86/ioemul: Account for ioemul_handle_quirk() in stub length check
The opcode potentially written into ctxt->io_emul_stub[] in the case
that ioemul_handle_quirk() is overriding the default logic isnt
accounted for in the build-time check that the stubs are large enough.
Introduce IOEMUL_QUIRK_STUB_BYTES and use for both the main and quirk
stub cases. As a slim optimisation, avoid writing out the default stub
when we know we are going to overwrite it.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
x86: Don't use potentially incorrect CPUID values for topology information
Intel says for CPUID leaf 0Bh:
"Software must not use EBX[15:0] to enumerate processor
topology of the system. This value in this field
(EBX[15:0]) is only intended for display/diagnostic
purposes. The actual number of logical processors
available to BIOS/OS/Applications may be different from
the value of EBX[15:0], depending on software and platform
hardware configurations."
And yet, we're using them to derive the number cores in a package
and the number of siblings in a core.
Derive the number of siblings and cores from EAX instead, which is
intended for that.
Signed-off-by: Jan H. Schönherr <jschoenh@amazon.de> Reviewed-by: Andrew Cooper <andrew.cooper3@citrix.com>
Andrew Cooper [Wed, 16 Aug 2017 17:06:59 +0000 (18:06 +0100)]
x86/entry: Remove support for partial cpu_user_regs frames
Save all GPRs on entry to Xen.
The entry_int82() path is via a DPL1 gate, only usable by 32bit PV guests, so
can get away with only saving the 32bit registers. All other entrypoints can
be reached from 32 or 64bit contexts.
This is part of XSA-254.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Wei Liu <wei.liu2@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
Roger Pau Monné [Thu, 4 Jan 2018 13:29:16 +0000 (14:29 +0100)]
x86/upcall: inject a spurious event after setting upcall vector
In case the vCPU has pending events to inject. This fixes a bug that
happened if the guest mapped the vcpu info area using
VCPUOP_register_vcpu_info without having setup the event channel
upcall, and then setup the upcall vector.
In this scenario the guest would not receive any upcalls, because the
call to VCPUOP_register_vcpu_info would have marked the vCPU as having
pending events, but the vector could not be injected because it was
not yet setup.
This has not caused issues so far because all the consumers first
setup the vector callback and then map the vcpu info page, but there's
no limitation that prevents doing it in the inverse order.
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
This patch adds the old value param and the onchangeonly option
to the VM_EVENT_REASON_MOV_TO_MSR event.
The param was added to the vm_event_mov_to_msr struct and to the
hvm_monitor_msr function. Finally I've changed the bool_t param
to a bool for the hvm_msr_write_intercept function.
Signed-off-by: Alexandru Isaila <aisaila@bitdefender.com> Acked-by: Tamas K Lengyel <tamas@tklengyel.com> Acked-by: Wei Liu <wei.liu2@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Thu, 4 Jan 2018 13:27:38 +0000 (14:27 +0100)]
x86/msr: Free msr_vcpu_policy during vcpu destruction
c/s 4187f79dc7 "x86/msr: introduce struct msr_vcpu_policy" introduced a
per-vcpu memory allocation, but failed to free it in the clean vcpu
destruction case.
This is XSA-253.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Fri, 2 Dec 2016 15:00:41 +0000 (15:00 +0000)]
xen/x86: Correct mandatory and SMP barrier definitions
Barriers are a complicated topic, a source of confusion, and their incorrect
use is a common cause of bugs. It really doesn't help when Xen's API is the
same as Linux, but its ABI different.
Bring the two back in line, so programmers stand a chance of actually getting
their usage correct.
Drop the links in the comment, both of which are now stale. Instead, refer to
the vendor system manuals in a generic way.
No functional change.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Reviewed-by: Dario Faggioli <dario.faggioli@citrix.com> Reviewed-by: Jan Beulich <jbeulich@suse.com>
Andrew Cooper [Fri, 2 Dec 2016 15:00:41 +0000 (15:00 +0000)]
xen/x86: Drop unnecessary barriers
x86's current implementation of wmb() is a compiler barrier. As a result, the
only change in this patch is to remove an mfence instruction from
cpuidle_disable_deep_cstate().
None of these barriers serve any purpose. They are not synchronising with
remote cpus, and their compiler-barrier properties are not needed for
correctness purposes.
Furthermore, these wmb()'s specifically do not want to turn into sfence
instructions in future changes where wmb()'s implementation is corrected.
Signed-off-by: Andrew Cooper <andrew.cooper3@citrix.com> Acked-by: Jan Beulich <jbeulich@suse.com>
Various minor optimizations in rb_erase():
- Avoid multiple loading of node->__rb_parent_color when computing parent
and color information (possibly not in close sequence, as there might
be further branches in the algorithm)
- In the 1-child subcase of case 1, copy the __rb_parent_color field from
the erased node to the child instead of recomputing it from the desired
parent and color
- When searching for the erased node's successor, differentiate between
cases 2 and 3 based on whether any left links were followed. This avoids
a condition later down.
- In case 3, keep a pointer to the erased node's right child so we don't
have to refetch it later to adjust its parent.
- In the no-childs subcase of cases 2 and 3, place the rebalance assigment
last so that the compiler can remove the following if(rebalance) test.
Also, added some comments to illustrate cases 2 and 3.
Signed-off-by: Michel Lespinasse <walken@google.com> Acked-by: Rik van Riel <riel@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 4f035ad67f4633c233cb3642711d49b4efc9c82d]
Ported to Xen.
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> Acked-by: Jan Beulich <jbeulich@suse.com>
rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()
An interesting observation for rb_erase() is that when a node has
exactly one child, the node must be black and the child must be red.
An interesting consequence is that removing such a node can be done by
simply replacing it with its child and making the child black,
which we can do efficiently in rb_erase(). __rb_erase_color() then
only needs to handle the no-childs case and can be modified accordingly.
Signed-off-by: Michel Lespinasse <walken@google.com> Acked-by: Rik van Riel <riel@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 46b6135a7402ac23c5b25f2bd79b03bab8f98278]
Ported to Xen.
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> Acked-by: Jan Beulich <jbeulich@suse.com>
When looking to fetch a node's sibling, we went through a sequence of:
- check if node is the parent's left child
- if it is, then fetch the parent's right child
This can be replaced with:
- fetch the parent's right child as an assumed sibling
- check that node is NOT the fetched child
This avoids fetching the parent's left child when node is actually
that child. Saves a bit on code size, though it doesn't seem to make
a large difference in speed.
Signed-off-by: Michel Lespinasse <walken@google.com> Acked-by: Rik van Riel <riel@redhat.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
[Linux commit 59633abf34e2f44b8e772a2c12a92132aa7c2220]
Ported to Xen.
Signed-off-by: Praveen Kumar <kpraveen.lkml@gmail.com> Acked-by: Jan Beulich <jbeulich@suse.com>
projects / xen.git / log